package th.retrofit.lib;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }

    @Override
    public String toString() {
        List<TreeNode> nodes = new ArrayList<>();
        List<TreeNode> children = new ArrayList<>();
        nodes.add(this);
        children.add(left);
        children.add(right);
        while (!isEmpty(children)) {
            List<TreeNode> temp = new ArrayList<>(children);
            children.clear();
            for (TreeNode node : temp) {
                if (node != null) {
                    children.add(node.left);
                    children.add(node.right);
                }
            }
            nodes.addAll(temp);
        }
        StringBuilder builder = new StringBuilder();
        builder.append('[');
        int size = nodes.size();
        for (int i = 0; i < size; i++) {
            TreeNode node = nodes.get(i);
            if (node != null) {
                builder.append(node.val);
            } else if (i != size - 1){
                builder.append("null");
            }
            if (i != size - 1) {
                builder.append(",");
            }
        }
        builder.append(']');
        if (builder.charAt(builder.length() - 2) == ',') {
            builder.deleteCharAt(builder.length() - 2);
        }
        return builder.toString();
    }

    private boolean isEmpty(List<TreeNode> list) {
        if (list.isEmpty()) return true;
        for (TreeNode node : list) {
            if (node != null) return false;
        }
        return true;
    }

    public static TreeNode array2Tree(Integer... arr) {
        TreeNode[] nodes = new TreeNode[arr.length];
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] != null) {
                nodes[i] = new TreeNode(arr[i]);
            } else {
                nodes[i] = null;
            }
        }
        return array2Tree(nodes);
    }

    public static TreeNode array2Tree(TreeNode... arr) {
        int size = arr.length;
        TreeNode head = arr[0];
        int index = 1;
        List<TreeNode> pre = new LinkedList<>();
        pre.add(head);
        while (index < size) {
            List<TreeNode> temp = new LinkedList<>();
            for (TreeNode node: pre) {
                if (node != null && index < size) {
                    node.left = arr[index++];
                    temp.add(node.left);
                    if (index < size) {
                        node.right = arr[index++];
                        temp.add(node.right);
                    }
                }
            }
            pre.clear();
            pre.addAll(temp);
        }
        return head;
    }

    public TreeNode copy() {
        TreeNode cur = new TreeNode();
        cur.val = this.val;
        if (this.left != null) {
            cur.left = this.left.copy();
        }
        if (this.right != null) {
            cur.right = this.right.copy();
        }
        return cur;
    }

    public static void main(String[] args) {
        TreeNode[] root = new TreeNode[13];
        root[0] = new TreeNode(5);
        root[1] = new TreeNode(4);
        root[2] = new TreeNode(8);
        root[3] = new TreeNode(11);
        root[4] = null;
        root[5] = new TreeNode(13);
        root[6] = new TreeNode(4);
        root[7] = new TreeNode(7);
        root[8] = new TreeNode(2);
        root[9] = null;
        root[10] = null;
        root[11] = new TreeNode(5);
        root[12] = new TreeNode(1);
        TreeNode head = TreeNode.array2Tree(root);
        System.out.println(head);
    }
}
